翻訳と辞書 Words near each other ・ Quasi alliance ・ Quasi at the Quackadero ・ Quasi corporation ・ Quasi Delay Insensitive ・ Quasi Fermi level ・ Quasi in rem jurisdiction ・ Quasi Object ・ Quasi Self Boot 93–96 ・ Quasi Universal Intergalactic Denomination ・ Quasi-algebraically closed field ・ Quasi-analog signal ・ Quasi-analytic function ・ Quasi-arithmetic mean ・ Quasi-bialgebra ・ Quasi-biennial oscillation ・ Quasi-bipartite graph ・ Quasi-birth–death process ・ Quasi-category ・ Quasi-commutative property ・ Quasi-compact morphism ・ Quasi-constitutionality ・ Quasi-continuous function ・ Quasi-contract ・ Quasi-criminal ・ Quasi-crystals (supramolecular) ・ Quasi-delict ・ Quasi-derivative ・ Quasi-elemental ・ Quasi-empirical method ・ Quasi-empiricism in mathematics Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Quasi-bipartite graph ： ウィキペディア英語版 Quasi-bipartite graph In the mathematical field of graph theory, an instance of the Steiner tree problem (consisting of an undirected graph ''G'' and a set ''R'' of terminal vertices that must be connected to each other) is said to be quasi-bipartite if the non-terminal vertices in ''G'' form an independent set, i.e. if every edge is incident on at least one terminal. This generalizes the concept of a bipartite graph: if ''G'' is bipartite, and ''R'' is the set of vertices on one side of the bipartition, the set to ''R'' is automatically independent. This concept was introduced by Rajagopalan and Vazirani 〔.〕 who used it to provide a (3/2 + ε) approximation algorithm for the Steiner tree problem on such instances. Subsequently the ε factor was removed by Rizzi〔.〕 and a 4/3 approximation algorithm was obtained by Chakrabarty et al.〔.〕 The same concept has been used by subsequent authors on the Steiner tree problem, e.g.〔.〕 Robins and Zelikovsky〔.〕 proposed an approximation algorithm for Steiner tree problem which on quasi-bipartite graphs has approximation ratio 1.28. The complexity of Robins and Zelikovsky's algorithm is ''O(''m'' ''n2'')'', where ''m'' and ''n'' are the numbers of terminals and non-terminals in the graph, respectively. Furthermore, Gröpl et al.〔.〕 gave a 1.217-approximation algorithm for the special case of ''uniformly quasi-bipartite'' instances. ==References== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Quasi-bipartite graph」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.